#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include "conio.h"

using namespace std;

map<pair<int,int>, int> i_s1_i_s2_to_length;

// non-recursive version
int find_length_of_the_CLS(const vector<int> &s1, const vector<int> &s2)
{
	vector<vector<int>> lens;
	lens.resize(s1.size());
	for (int i = 0; i < s1.size(); ++i)
		lens[i].resize(s2.size());

	for (int i = 0; i < s1.size(); ++i)
	{
		for (int j = 0; j < s2.size(); ++j)
		{
			if (s1[i] == s2[j])
			{
				if (i == 0 || j == 0)
					lens[i][j] = 1;
				else
					lens[i][j] = lens[i-1][j-1] + 1;
			}
			else
			{
				if (i == 0 || j == 0)
					lens[i][j] = 0;
				else
					lens[i][j] = max(lens[i-1][j], lens[i][j-1]);
			}
		}
	}
	return lens[s1.size()-1][s2.size()-1];
}

// recursive version
int cls_recursive(const vector<int> &s1, const vector<int> &s2, int i_s1, int i_s2)
{
	if (i_s1 < 0 || i_s2 < 0)
		return 0;
	
	if (s1[i_s1] == s2[i_s2])
	{
		auto found = i_s1_i_s2_to_length.find(make_pair(i_s1, i_s2));
		if (found != i_s1_i_s2_to_length.end())
			return found->second;

		int len = cls_recursive(s1, s2, i_s1-1, i_s2-1) + 1;
		i_s1_i_s2_to_length.insert(make_pair(make_pair(i_s1, i_s2), len));
		return len;
	}
	else
	{
		int len_1, len_2;

		auto found = i_s1_i_s2_to_length.find(make_pair(i_s1-1, i_s2));
		if (found != i_s1_i_s2_to_length.end())
			len_1 = found->second;
		else
			len_1 = cls_recursive(s1, s2, i_s1-1, i_s2);

		found = i_s1_i_s2_to_length.find(make_pair(i_s1, i_s2-1));
		if (found != i_s1_i_s2_to_length.end())
			len_2 = found->second;
		else
			len_2 = cls_recursive(s1, s2, i_s1, i_s2-1);

		i_s1_i_s2_to_length.insert(make_pair(make_pair(i_s1-1, i_s2), len_1));
		i_s1_i_s2_to_length.insert(make_pair(make_pair(i_s1, i_s2-1), len_2));

		return max(len_1, len_2);
	}
}

int find_length_of_the_CLS_recursive(const vector<int> &s1, const vector<int> &s2)
{
	return cls_recursive(s1, s2, s1.size()-1, s2.size()-1);
}

// first attempt
int find_length_of_the_CLS_first_version(const vector<int> &s1, const vector<int> &s2)
{
	vector<int> lengths(s2.size(), 0),
		prev_LIS_element_idx(s2.size(), -1),
		cur_match_index;

	for (int i_s1 = 0; i_s1 < static_cast<int>(s1.size()); ++i_s1)
	{
		int cur_elem = s1[i_s1];
		for (int i_s2 = static_cast<int>(s2.size()) - 1; i_s2 >= 0; --i_s2)
		{
			if (cur_elem == s2[i_s2])	// match found
			{
				cur_match_index.push_back(i_s2);
				if (lengths[i_s2] == 0)
					lengths[i_s2] = 1;
			}
			else if (cur_match_index.size() > 0)	// have matches in the pool
			{
				for (int i_match = 0; i_match < static_cast<int>(cur_match_index.size()); ++i_match)
				{
					if (lengths[i_s2] >= lengths[cur_match_index[i_match]])	// found LIS to the left
					{
						lengths[cur_match_index[i_match]] = lengths[i_s2] + 1;
						prev_LIS_element_idx[cur_match_index[i_match]] = i_s2;
					}
				}
			}			
		}
		cur_match_index.clear();
	}

	vector<int> lcs;
	int max_len_idx = max_element(lengths.begin(), lengths.end()) - lengths.begin();
	while (max_len_idx != -1)
	{		
		lcs.push_back(s2[max_len_idx]);
		max_len_idx = prev_LIS_element_idx[max_len_idx];
	}
	cout << "Longest increasing subsequence:" << endl;
	
	for_each(lcs.rbegin(), lcs.rend(), [&] (int v) { cout << v << " "; } );

	return *max_element(lengths.begin(), lengths.end());
}

void main()
{
	int len_1, len_2;
	vector<int> s1, s2;

	cout << "input length of the first sequence : " << endl;
	cin >> len_1;
	cout << "input first sequence : " << endl;
	s1.resize(len_1);
	for (int i = 0; i < len_1; ++i)
		cin >> s1[i];
		//s1[i] = i;

	cout << "input length of the second sequence : " << endl;
	cin >> len_2;
	s2.resize(len_2);
	cout << "input second sequence : " << endl;
	for (int i = 0; i < len_2; ++i)
		cin >> s2[i];
		//s2[i] = 2*i;

	cout << endl << "length of the LCS = " << find_length_of_the_CLS(s1, s2);
	_getch();
}